/*
 * @lc app=leetcode id=22 lang=cpp
 *
 * [22] Generate Parentheses
 */
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string s = "";
        dfs(s, n, 0, 0, ret);
        return ret;
    }

    void dfs(string& s, int n, int left, int right, vector<string>& ret) {

        if (left > n || right > n) {
            return;
        }

        if (left < right) {
            return;
        }

        if (left == n && right == n) {
            ret.push_back(s);
            return ;
        }

        if (left < n) {
            s.push_back('(');
            dfs(s, n, left+1, right, ret);
            s.pop_back();
        }

        if (right < n && right < left) {
            s.push_back(')');
            dfs(s, n, left, right+1, ret);
            s.pop_back();
        }
    }
};

